package lab.chapter;

import lombok.Getter;
import lombok.Setter;

import java.util.*;

/**
 * 表达正则文法,能够表达 EBNF 的对象
 * 1. 每个grammarNode 可以有多个子节点
 * 2. 子节点之间可以是And、or关系，由属性 type 确定
 * 3. minTimes 和 maxTimes确定了节点的重复次数。对于+号，minTimes=1，maxTimes=-1，-1代表很多个。
 * 4. 节点可以有名字。即词法规则左边部分。如果没有名称，系统会根据它的父节点的名称生成默认名字，以下划线开头。如_and_or_1
 */
@Getter
@Setter
public class GrammarNode {
    // 子节点
    private List<GrammarNode> children = new LinkedList<>();

    // 节点类型
    private GrammarNodeType type = null;
    // 能匹配字符的集合。charset可以是一个树状结构，由多个子结点构成。
    private CharSet charSet = null;
    // 节点名字
    private String name = null;
    // 节点可以重复的次数
    private int minTimes = 1;
    private int maxTimes = 1;

    // 语法规则中的 Token
    private Token token = null;
    // 是否忽略空白字符等
    private boolean neglect = false;

    // 常用 grammar node
    public static GrammarNode EPSILON = new GrammarNode(GrammarNodeType.Epsilon);

    protected GrammarNode(GrammarNodeType type) {
        this.type = type;
    }

    protected GrammarNode(String name, GrammarNodeType type) {
        this.name = name;
        this.type = type;
    }

    protected GrammarNode(String name, GrammarNodeType type, GrammarNode child, Token token) {
        this.name = name;
        this.type = type;
        this.children.add(child);
        this.token = token;
    }

    protected GrammarNode(String name, GrammarNodeType type, List<GrammarNode> children, Token token) {
        this.name = name;
        this.type = type;
        this.children.addAll(children);
        this.token = token;
    }

    protected GrammarNode(Token token) {
        this.token = token;
    }

    protected GrammarNode(CharSet charSet) {
        this.type = GrammarNodeType.Char;
        this.charSet = charSet;
    }

    protected GrammarNode(String name, CharSet charSet) {
        this.name = name;
        this.type = GrammarNodeType.Char;
        this.charSet = charSet;
    }

    // 创建子节点
    protected GrammarNode createChild(CharSet charSet) {
        GrammarNode grammarNode = new GrammarNode(charSet);
        addChild(grammarNode);
        return grammarNode;
    }

    protected GrammarNode createChild(String name, CharSet charSet) {
        GrammarNode grammarNode = new GrammarNode(name, charSet);
        addChild(grammarNode);
        return grammarNode;
    }

    protected GrammarNode createChild(GrammarNodeType type) {
        GrammarNode grammarNode = new GrammarNode(type);
        addChild(grammarNode);
        return grammarNode;
    }

    protected GrammarNode createChild(String name, GrammarNodeType type) {
        GrammarNode grammarNode = new GrammarNode(name, type);
        addChild(grammarNode);
        return grammarNode;
    }

    protected GrammarNode createChild(Token token) {
        GrammarNode grammarNode = new GrammarNode(token);
        addChild(grammarNode);
        return grammarNode;
    }

    /**
     * 添加子节点，并创建默认名称. 以下划线开头
     * @param child 子节点
     */
    protected void addChild(GrammarNode child) {
        children.add(child);
        if (child.name == null) {
            child.name = "_"+child.type+children.size();
            if (this.name != null) {
                child.name = this.name + child.name;
            }
            if (child.name.charAt(0) != '_') {
                child.name = "_"+child.name;
            }
        }
    }

    /**
     * 是否显示命名的子节点。词法规则中的 Token，语法规则中的非终结符，都有名字
     * @return bool
     */
    protected boolean isNamedNode() {
        return name != null && name.length() > 1 && name.charAt(0) != '_';
    }

    /**
     * 只读子节点列表。
     * @return list
     */
    public List<GrammarNode> children() {
        return Collections.unmodifiableList(children);
    }

    public int getChildCount() {
        return children.size();
    }

    // 获取子节点
    public GrammarNode getChild(int index) {
        if (index < 0 || index > children.size()) {
            return null;
        }
        return children.get(index);
    }

    public GrammarNodeType getType() {
        return type;
    }

    public String getName() {
        return name;
    }

    public String getGrammarName() {
        if (token != null) {
            return token.getType();
        } else if (isNamedNode()) {
            return name;
        }
        return null;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        // 类型相同
        GrammarNode node = (GrammarNode) obj;
        if (node.type != type) {
            return false;
        }
        // 名称相同
        if (node.name == null) {
            if (name != null) {
                return false;
            }
        } else {
            if (!node.name.equals(name)) {
                return false;
            }
        }

        // 比较 token
        if (type == GrammarNodeType.Token) {
            return token.equals(node.token);
        } else if (type == GrammarNodeType.Epsilon) {
            return true;
        } else if (type == GrammarNodeType.Char) {
            return charSet.equals(node.charSet);
        }

        // 子节点也相同
        if (children.size() != node.children.size()) {
            return false;
        }

        for (int i = 0; i < children().size(); i++) {
            if (!children.get(i).equals(node.children.get(i))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 以易读方式显示
     * @return string
     */
    @Override
    public String toString() {
        if (type == GrammarNodeType.Epsilon)
            return "ε";

        String rtn;
        if (charSet != null) {
            rtn = charSet.toString();
        } else if (token != null) {
            if (token.getText() != null) {
                rtn = "'" + token.getText() + "'";
            } else {
                rtn = token.getType();
            }
        } else if (name != null) {
            rtn = name;
        } else if (type != null) {
            rtn = type.toString();
        } else {
            rtn = "GrammarNode";
        }

        if (minTimes != 1 || maxTimes != 1) {
            if (minTimes == 0 && maxTimes == -1) {
                rtn += "*";
            } else if (minTimes == 0 && maxTimes == 1) {
                rtn += "?";
            } else if (minTimes == 1 && maxTimes == -1) {
                rtn += "+";
            } else {
                rtn += "{" + minTimes + "," + maxTimes + "}";
            }
        }
        return rtn;
    }

    protected void setRepeatTimes(int minTimes, int maxTimes) {
        this.minTimes = minTimes;
        this.maxTimes = maxTimes;
    }


    /**
     * 文本形式显示节点。显示结果格式与 Antlr 的文法格式一致。
     * 对于命名的节点，需要把它的子节点都显示出来。
     * 比如，primary 节点： primary: ID | INT_LITERAL | add
     * @return string
     */
    protected String getText() {
        String delim = null;
        if (type == GrammarNodeType.And) {
            delim = " ";
        } else if (type == GrammarNodeType.Or) {
            delim = " | ";
        }

        StringBuilder sb = new StringBuilder();
        if (children.size() > 0) {
            for (int i = 0; i < children.size(); i++) {
                if (i > 0) {
                    sb.append(delim);
                }
                GrammarNode child = children.get(i);
                if (child.isNamedNode()) {
                    sb.append(child.toString());
                } else {
                    sb.append(child.getText());
                }
            }
        } else {
            sb.append(this.toString());
        }
        String rtn = sb.toString();
        if (isNamedNode()) {
            rtn = wrapNamedNode(rtn);
        } else {
            if (type == GrammarNodeType.Or) {
                rtn = "(" + rtn + ")";
            }
        }
        return rtn;
    }

    private String wrapNamedNode(String s) {
        if (name != null) {
            String header = name;
            if (name.length() <= 3) {
                header += "\t";
            }
            header += "\t: ";
            return header + s + " ;";
        }
        return s;
    }

    /**
     * 打印当前节点
     */
    protected void  dump() {
        if (isGraph(this, new HashSet<>())) {
            dumpGraph(this, new HashSet<>());
        } else {
            dumpTree(this, "");
        }
    }

    /**
     * 以某节点为起始节点，通过是否有环，判断是树还是图。
     * @param node 起始节点
     * @param scannedNodes 检查过的节点
     * @return boolean
     */
    private static boolean isGraph(GrammarNode node, Set<GrammarNode> scannedNodes) {
        scannedNodes.add(node);
        for (GrammarNode child : node.children) {
            if (scannedNodes.contains(child)) {
                return true;
            }
        }

        for (GrammarNode child : node.children) {
            boolean rtn = isGraph(child, scannedNodes);
            if (rtn) {
                return true;
            }
        }
        return false;
    }

    /**
     * 打印图。
     * @param node 起始节点
     * @param dumpedNodes 已经打印的节点
     */
    private static void dumpGraph(GrammarNode node, Set<GrammarNode> dumpedNodes) {
        if (node.isNamedNode()) {
            System.out.println(node.getText());
        }
        dumpedNodes.add(node);
        for (GrammarNode child : node.children) {
            if (!dumpedNodes.contains(child)) {
                dumpGraph(child, dumpedNodes);
            }
        }
    }

    /**
     * 打印树状结构
     * @param node 起始节点
     * @param indent 缩进。
     */
    private static void dumpTree(GrammarNode node, String indent) {
        if (node.isNamedNode()) {
            System.out.println(indent + node.getText());
        } else {
            // 此处调用 node.toString()，即 System.out.println(indent + node.toString());
            System.out.println(indent + node);
        }
        for (GrammarNode child : node.children) {
            dumpTree(child, indent + "\t");
        }
    }

    /**
     * 该节点是否可空，即能否返回 Epsilon。
     * 1. 如果是Epsilon 节点，或者*、？，可空。
     * 2. And 节点，所有节点都可空时，可空
     * 3. Or 节点，任意子节点可空时，可空
     * 4. 其它，不为空
     * @return 是否可空
     */
    public boolean isNullable() {
        boolean rtn = false;
        if (this.minTimes == 0 || this.type == GrammarNodeType.Epsilon) {
            return true;
        } else if (this.type == GrammarNodeType.And) {
            boolean allNullable = true;
            for (GrammarNode child : children) {
                if (!child.isNamedNode()) {
                    allNullable = false;
                    break;
                }
            }
            rtn = allNullable;
        } else if (this.type == GrammarNodeType.Or) {
            boolean anyNullable = false;
            for (GrammarNode child : children) {
                if (child.isNullable()) {
                    anyNullable = true;
                    break;
                }
            }
            rtn = anyNullable;
        }
        return rtn;
    }

    /**
     * 获得以本节点为起始节点, 所能到达的所有语法节点
     * @return 所有节点
     */
    protected List<GrammarNode> getAllNodes() {
        List<GrammarNode> allNodes = new LinkedList<>();
        getAllNodes(this, allNodes);
        return allNodes;
    }

    private static void getAllNodes(GrammarNode node, List<GrammarNode> allNodes) {
        allNodes.add(node);
        for (GrammarNode child : node.children) {
            if(!allNodes.contains(child)) {
                getAllNodes(child, allNodes);
            }
        }
    }

    // 是否是叶子节点
    public boolean isLeaf() {
        return children.size() == 0;
    }

    // 是否代表一个token
    public boolean isToken() {
        return token != null;
    }

    public boolean isNeglect() {
        return neglect;
    }
}
